package leetcode.editor.cn.q1_300.q50;

/**
 * @author qidi
 * @date 2021-12-13 15:43:19
 */
class Q0067_AddBinary {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String addBinary(String a, String b) {
            int tmp = 0;
            StringBuilder sb = new StringBuilder();

            int size = Math.min(a.length(), b.length());

            int i = 0;

            while (i < size) {
                char ac = a.charAt(a.length() - i - 1);
                char bc = b.charAt(b.length() - i - 1);
                if (ac == '1' && bc == '1') {
                    if (tmp == 0) {
                        sb.insert(0, 0);
                    } else {
                        sb.insert(0, 1);
                    }
                    tmp = 1;
                } else {
                    if (ac == '1' || bc == '1') {
                        if (tmp == 0) {
                            sb.insert(0, 1);
                            tmp = 0;
                        } else {
                            sb.insert(0, 0);
                            tmp = 1;
                        }
                    } else {
                        sb.insert(0, tmp);
                        tmp = 0;
                    }
                }
                i++;
            }

            String aa = a.length() > b.length() ? a : b;

            b = a.length() < b.length() ? a : b;

            tmp = getTmp(aa, tmp, sb, aa.length() - b.length() - 1);

            if (tmp == 1) sb.insert(0, 1);

            return sb.toString();
        }

        private int getTmp(String a, int tmp, StringBuilder sb, int i) {
            while (i >= 0) {
                if (a.charAt(i) == '1' && tmp == 1) {
                    sb.insert(0, 0);
                    tmp = 1;
                } else {
                    sb.insert(0, a.charAt(i) == '1' || tmp == 1 ? 1 : 0);
                    tmp = 0;
                }
                i--;
            }
            return tmp;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0067_AddBinary().new Solution();
        System.out.println(solution.addBinary("100", "110010"));
        System.out.println(solution.addBinary("11", "1"));
        System.out.println(solution.addBinary("1010", "1011"));
    }
}